I'm having the same issue.
Probably unrelated, but whats odd is that I got an alert about my FTP server being offline (external host that scans my FTP, and alerts issues) at the exact same time that I got these errors in my message tracking logs..
The ESXi server that hosts the FTP server only additionally hosts the Domain controller.
Server 2012 standard, with Exchange 2013 Version 15.0 (Build 712.22)
EDIT: digging a little deeper, a fellow tech was talking to the ISP at this time and the ISP rebooted our cable modem... shouldn't Exchange just queue the message instead of drop it if it can't establish a connection outbound?
Also, these messages were all generated from a 3rd party software that is configured to send messages through my exchange server. receive connector is good since 99% of the messages generated are received correctly.